package geekstudy.week1;

import java.util.*;

/**
 *
 * 8. 合并两个有序数组
 * https://leetcode-cn.com/problems/merge-sorted-array/
 *
 *
 */
public class Week1MergeSortedArray {

    public void mergeWithCollection(int[] nums1, int m, int[] nums2, int n) {
        List<Integer> demoList = new ArrayList<Integer>();
        for(int first = 0; first < m; first++) {
            demoList.add(nums1[first]);
        }
        for(int second = 0; second < nums2.length; second++) {
            demoList.add(nums2[second]);
        }
        Collections.sort(demoList);

        // Iterator<Integer> iterator = demoSet.iterator();
        for(int size = 0; size < demoList.size(); size++) {
            nums1[size] = demoList.get(size);
        }
        System.out.println("nums1 " + Arrays.toString(nums1));
    }

    public void mergeAppend(int[] nums1, int m, int[] nums2, int n) {
        System.out.print("输入参数 nums1: " + Arrays.toString(nums1) + " nums2: " + Arrays.toString(nums2));
        for(int secondIndex = 0; secondIndex < nums2.length; secondIndex++) {
            // 将 num2 元素 一次加入 第一个数组 并重新排序
            nums1[m + secondIndex] = nums2[secondIndex];
            sortArrayLastElement(nums1, m + secondIndex);
        }

        System.out.println(" nums1 处理结果: " + Arrays.toString(nums1));
    }

    /**
     * 对有序数组 最新加入的末尾数值排序
     * @param array
     * @param lastIndex
     */
    public void sortArrayLastElement(int[] array, int lastIndex) {
        for(int size = lastIndex; size > 0; size--) {
            if(size - 1 >= 0 ) {
                if(array[size] < array[size - 1]) {
                    // 当元素 比前一个元素小时 往前移动一位
                    int temp = array[size - 1];
                    array[size - 1] = array[size];
                    array[size] = temp;
                } else {
                    // 当元素 比前一个元素大 或者相等 终止循环
                    break;
                }

            }
        }
    }

    public static void main(String[] args) {
        // 输入1 nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
        // 输出1 [1,2,2,3,5,6]

        // nums1 = [1], m = 1, nums2 = [], n = 0
        // [1]


        // int[] array1 = new int[]{1, 2, 3, 0, 0, 0};
        Week1MergeSortedArray mergeSortedArray = new Week1MergeSortedArray();
        // mergeSortedArray.moveOne(array1, 2, 9);

        // 测试
        int[] test1Nums1 = new int[]{1, 2, 3, 0, 0, 0};
        int[] test1Nums2 = new int[]{2, 5, 6};
        mergeSortedArray.mergeAppend(test1Nums1, 3, test1Nums2, 3);


        // mergeSortedArray.merge(test2Nums1, 1, test2Nums2, 0);

        // 未通过测试

        // mergeSortedArray.merge(test3Nums1, 1, test3Nums2, 1);

        // 未通过测试 0 参与排序
        int[] test4Nums1 = new int[]{-1, 0, 0, 3, 3, 3, 0, 0, 0 };
        int[] test4Nums2 = new int[]{1, 2, 2 };
        // mergeSortedArray.merge(test4Nums1, 6, test4Nums2, 3);

        int[] test5Nums1 = new int[]{-1, 3, 0, 0, 0, 0, 0};
        int[] test5Nums2 = new int[]{0, 0, 1, 2, 3};
        // mergeSortedArray.merge(test5Nums1, 2, test5Nums2, 5);

        int[] test6Nums1 = new int[]{0 };
        int[] test6Nums2 = new int[]{1 };
        // mergeSortedArray.merge(test6Nums1, 0, test6Nums2, 1);

        int[] test7Nums1 = new int[]{1, 0};
        int[] test7Nums2 = new int[]{2};
        // mergeSortedArray.merge(test7Nums1, 1, test7Nums2, 1);

        int[] test8Nums1 = new int[]{1, 2, 3, 0, 0, 0};
        int[] test8Nums2 = new int[]{4, 5, 6};
        // mergeSortedArray.mergeDemo(test8Nums1, 3, test8Nums2, 3);
        // mergeSortedArray.merge(test8Nums1, 3, test8Nums2, 3);


    }
}
